1. Related Applications
The present application discloses certain aspects of a computing system that is further described in the following U.S. patent applications filed concurrently with the present application: Evans et al., AN INTERFACE BETWEEN A SYSTEM CONTROL UNIT AND A SERVICE PROCESSING UNIT OF A DIGITAL COMPUTER, Ser. No. 07/306,325 filed Feb. 3, 1989; Arnold et al., METHOD AND APPARATUS FOR INTERFACING A SYSTEM CONTROL UNIT FOR A MULTIPROCESSOR SYSTEM WITH THE CENTRAL PROCESSING UNITS, Ser. No. 07/306,837 filed Feb. 3, 1989; Gagliardo et al., METHOD AND MEANS FOR INTERFACING A SYSTEM CONTROL UNIT FOR A MULTI-PROCESSOR SYSTEM WITH THE SYSTEM MAIN MEMORY, Ser. No. 07/306,326 filed Feb. 3, 1989 now abandoned; D. Fite et al., METHOD AND APPARATUS FOR RESOLVING A VARIABLE NUMBER OF POTENTIAL MEMORY ACCESS CONFLICTS IN A PIPELINED COMPUTER SYSTEM, Ser. No. 07/306,767 filed Feb. 3, 1989; D. Fite et al., DECODING MULTIPLE SPECIFIERS IN A VARIABLE LENGTH INSTRUCTION ARCHITECTURE, Ser. No. 07/307,347 filed Feb. 3, 1989; D. Fite et al., VIRTUAL INSTRUCTION CACHE REFILL ALGORITHM, Ser. No. 07/306,831 filed Feb. 3, 1989; Murray et al., PIPELINE PROCESSING OF REGISTER AND REGISTER MODIFYING SPECIFIERS WITHIN THE SAME INSTRUCTION, Ser. No. 07/306,833 filed Feb. 3, 1989; Murray et al., MULTIPLE INSTRUCTION PREPROCESSING SYSTEM WITH DATA DEPENDENCY RESOLUTION FOR DIGITAL COMPUTERS, Ser. No. 07/306,773 filed Feb. 3, 1989; Murray et al., PREPROCESSING IMPLIED SPECIFIERS IN A PIPELINED PROCESSOR, Ser. No. 07/306,846 filed Feb. 3, 1989; D. Fite et al., METHOD OF BRANCH PREDICTION, Ser. No. 07/306,760 filed Feb. 3, 1989; Fossum et al., PIPELINED FLOATING POINT ADDER FOR DIGITAL COMPUTER, Ser. No. Ser. No. 07/306,343 filed Feb. 3, 1989 now U.S. Pat. No. 4,994,996; Grundmann et al., SELF TIMED REGISTER FILE, Ser. No. 07/306,445 filed Feb. 3, 1989; Beaven et al., METHOD AND APPARATUS FOR DETECTING AND CORRECTING ERRORS IN A PIPELINED COMPUTER SYSTEM, Ser. No. 07/306,838 filed Feb. 3, 1989 and issued as U.S. Pat. No. 4,982,402 on Jan. 1, 1991; Flynn et al., METHOD AND MEANS FOR ARBITRATING COMMUNICATION REQUESTS USING A SYSTEM CONTROL UNIT IN A MULTI-PROCESSOR SYSTEM, Ser. No. 07/306,871 filed Feb. 3, 1989; E. Fite et al., CONTROL OF MULTIPLE FUNCTION UNITS WITH PARALLEL OPERATION IN A MICROCODED EXECUTION UNIT, Ser. No. 07/306,832 filed Feb. 3, 1989 now U.S. Pat. No. 5,067,069; Webb, Jr. et al., PROCESSING OF MEMORY ACCESS EXCEPTIONS WITH PREFETCHED INSTRUCTIONS WITHIN THE INSTRUCTION PIPELINE OF A VIRTUAL MEMORY SYSTEM-BASED DIGITAL COMPUTER, Ser. No. 07/306,866 filed Feb. 3, 1989 now U.S. Pat. No. 4,985,825; Heterhington et al., METHOD AND APPARATUS FOR CONTROLLING THE CONVERSION OF VIRTUAL TO PHYSICAL MEMORY ADDRESSES IN A DIGITAL COMPUTER SYSTEM, Ser. No. 07/306,544 filed Feb. 3, 1989 now abandoned; Hetherington et al., WRITE BACK BUFFER WITH ERROR CORRECTING CAPABILITIES, Ser. No. 07/306,703 filed Feb. 3, 1989 now U.S. Pat. No. 4,895,041; Chinnasway et al., MODULAR CROSSBAR INTERCONNECTION NETWORK FOR DATA TRANSACTIONS BETWEEN SYSTEM UNITS IN A MULTI-PROCESSOR SYSTEM, Ser. No. 07/306,336 filed Feb. 3, 1989, and issued as U.S. Pat. No. 4,968,977 on Nov. 6, 1990; Polzin et al., METHOD AND APPARATUS FOR INTERFACING A SYSTEM CONTROL UNIT FOR A MULTI-PROCESSOR SYSTEM WITH INPUT/OUTPUT UNITS, Ser. No. 07/306,862 filed Feb. 3, 1989, and issued as U.S. Pat. No. 4,965,793 on Oct. 23, 1990; Gagliardo et al., MEMORY CONFIGURATION FOR USE WITH MEANS FOR INTERFACING A SYSTEM CONTROL UNIT FOR A MULTI-PROCESSOR SYSTEM WITH THE SYSTEM MAIN MEMORY, Ser. No. 07/306,404 filed Feb. 3, 1989 now U.S. Pat. No. 5,043,874; and Gagliardo et al., METHOD AND MEANS FOR ERROR CHECKING OF DRAM-CONTROL SIGNALS BETWEEN SYSTEM MODULES, Ser. No. 07/306,836 filed Feb. 2, 1989 now abandoned.
2. Technical Field
This invention relates generally to a virtual instruction cache (VIC) of a high-speed digital computer and, more particularly, to controlling the VIC to prefetch and align variable length instructions.
Description of Related Art
In the field of high speed computers, most advanced computers pipeline the entire sequence of instruction activities. A prime example is the VAX 8600 computer manufactured and sold by Digital Equipment Corporation, 111 Powdermill Road, Maynard Mass. 97154-1418. The instruction pipeline for the VAX 8600 is described in T. Fossum et al. "An Overview of the VAX 8600 System," Digital Technical Journal. No. 1, Aug. 1985, pp. 8-23. Separate pipeline stages are provided for instruction fetch, instruction decode, operand address generation, operand fetch, instruction execute, and result store.
To make effective use of this pipelining capability, it is desirable to keep each stage of the pipeline occupied, performing its intended function on the next instruction to be executed. In order to do this, the instruction fetch stage must retrieve an instruction and pass it to the next stage between each transition of the system clock. Otherwise, such a disruption in the instruction stream causes the pipeline to drain, necessitating a time-consuming restart of the entire pipeline. Of course, the purpose of the pipeline is to increase the overall speed of the computer. Thus, it is highly advantageous to avoid these situations where the pipeline is interrupted.
However, the instruction set employed in some computers is of the variable length type, thereby forcing the instruction buffer to have added complexity. In other words, until the instruction (opcode) is decoded, the instruction buffer does not "know" how many of the subsequent bytes of the instruction stream belong with the current instruction. Therefore, the instruction buffer can only respond by loading a preselected number of bytes of the instruction stream, which may or may not include an entire instruction. The instruction decoder will only consume those bytes associated with the immediate instruction. Thereafter, the instruction buffer must determine how many of the present bytes were used by the decoder, shift the unused bytes into the lowest order locations, and then fill the empty buffer locations with subsequent bytes of the instruction stream.
Reference to the main memory to retrieve these subsequent bytes of instruction stream necessarily involves multiple clock cycles. To avoid accessing main memory, many digital computers include a high speed cache between the processing unit and the main memory. Access to this cache takes only a small number of cycles of the processor's clock but often involves translating virtual addresses to physical addresses. To further accelerate the access to the instruction stream, some systems dedicate a cache solely to store the instructions. The access to this "instruction cache" often does not entail translating from virtual to physical addresses as the instructions are stored under their virtual addresses. This access to the instruction stream in a high speed virtual instruction cache may only involve one cycle of the processor's clock.
The virtual instruction cache, however, contains only a portion of the main memory, each reference to the virtual instruction cache involves comparing the requested address with the desired address to first determine if the desired instruction stream is present and then retrieving the requested instruction stream. Therefore, owing to the variable length nature of the instruction set, the instruction buffer cannot predict whether a reference to the VIC will be required by the instruction currently being decoded.
To prevent numerous references to the virtual instruction cache, a prefetch buffer is provided to maintain a preselected number of the subsequent bytes of instruction stream which are expected to be used by the instruction decoder. This process forestalls the inevitable reference to the virtual instruction cache.
Since the virtual instruction cache contains only a portion of the instruction stream, refills to the instruction buffer can result in "misses" in the virtual instruction cache, which require fetches from the main memory. These main memory fetches generally require many clock cycles, thereby interrupting the pipeline.